package net.tp.algo.knapsack;

/**
 *
 * <p>Binary Knapsack or 0/1 Knapsack Problem.</p>
 *
 *
 *
 *
 * @author Trung Phan
 *
 */
public class BinaryKnapsack {


    /**
     *
     * <p>Binary Integer Knapsack Problem.</p>
     *
     * <p>Assumption:</p>
     * <ul>
     *     <li>Sizes are integer. As sizes are integer, the capacity should be integer (otherwise round down the capacity).</li>
     *     <li>Capacity &lt; sum(sizes). Otherwise, just include every items into the solution.</li>
     * </ul>
     *
     * <p>Dynamic Programming:</p>
     * <ul>
     *     <li>Let {@code M[i][c]} be the maximal value obtained from items {@code 1..i} with knapsack capacity of {@code c}.</li>
     * </ul>
     *
     * @param sizes item sizes
     * @param values item values
     * @param capacity capacity
     * @return items fit into the knapsack
     * @time $O(nC)$
     * @space $O(nC)$
     *
     *
     */
    public static int[] find(int[] sizes, double[] values, int capacity) {

        int N = sizes.length;

        double[][] M = new double[N + 1][capacity + 1];

        for (int i = 1; i <= N; i++) {
            for (int c = 1; c <= capacity; c++) {
                M[i][c] = M[i-1][c];
                if (c >= sizes[i-1] && M[i][c] < values[i-1] + M[i-1][c - sizes[i-1]]) {
                    M[i][c] = values[i-1] + M[i-1][c - sizes[i-1]];
                }
            }
        }

        int[] result = new int[N];
        int c = capacity;
        for (int i = N; i >= 1; i--) {
            if (M[i][c] > M[i-1][c]) {
                c -= sizes[i-1];
                result[i-1]++;
            }
        }

        return result;
    }

    /**
     *
     *
     * @param sizes item sizes
     * @param values item values
     * @param capacity capacity
     * @return items fit into the knapsack
     * @time $O(nV)$ where $V=∑v_i$
     * @space $O(nV)$
     *
     */
    public static int[] find2(double[] sizes, int[] values, double capacity) {
        int N = sizes.length;
        int V = 0;
        for (int v : values) V+= v;

        double[][] M = new double[N+1][V+1]; // M[i][v] min total size of items[1..i] for exact value v
        for (int i = 1; i < V+1; i++) M[0][i] = Double.MAX_VALUE;

        for (int i = 1; i <= N; i++) {
            for (int v = 1; v <= V; v++) {
                M[i][v] = M[i-1][v];
                if (v >= values[i-1] && M[i - 1][v - values[i - 1]] != Double.MAX_VALUE) {
                    double s = sizes[i-1] + M[i - 1][v - values[i - 1]];
                    if (M[i][v] > s) {
                        M[i][v] = s;
                    }
                }
            }
        }

        int v = V;
        while (v >= 1 && M[N][v] > capacity) v--;

        int[] result = new int[N];
        for (int i = N; i >= 1; i--) {
            if (M[i][v] != M[i-1][v]) {
                v -= values[i-1];
                result[i-1]++;
            }
        }

        return result;
    }



    public static int[] solve3(double[] sizes, double[] values, double capacity, double epsilon) {



        return null;
    }
}
